<?php 
//输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
/*class TreeNode{
    var $val;
    var $left = NULL;
    var $right = NULL;
    function __construct($val){
        $this->val = $val;
    }
}*/
function HasSubtree($pRoot1, $pRoot2)
{
    if($pRoot1 == NULL || $pRoot2 == NULL) return false;
    return isSubtree($pRoot1,$pRoot2);
}

function isSubtree($pa,$pb)
{
	if($pa == NULL) return false;
	if($pa->val == $pb->val) $ret=isSubtreeTmo($pa,$pb);//节点值相同，继续判断左右子树;
	if($ret) return true;//左右子树都相同，返回真。
	$ret = isSubtree($pa->left,$pb);//左右节点不一样，在pa的左子树中继续查找
	if($ret) return true;//如果找到了，返回真。
	$ret = isSubtree($pa->right,$pb);//左右节点不一样，在pa的右子树中继续查找
	if($ret) return true;//如果找到了，返回真。
	else return false;
	//左右子树都找不到，就返回假。
}

function isSubtreeTmo($pa,$pb)
{
	if($pb == NULL) return true;//如果为空，说明完全匹配
	if($pa == NULL && $pb!=NULL) return false;//如果 A 树先空，而 B 树还没空，匹配失败
	return $pa->val==$pb->val && isSubtreeTmo($pa->left,$pb->left) && isSubtreeTmo($pa->right,$pb->right);//如果节点值相同，继续匹配左子树和右子树
}
	
?>